package com.kitty.record.kittyalgorithm.ds.link;

/**
 * @author shenshen.qian@amh-group.com
 * @version 0.0.1
 * @date 2022/2/9 15:21
 */
public class DoubleLink<T> {

    private DNode<T> mHead;

    private int mCount;


    public DoubleLink() {
        //构造函数，初始化链表
        mHead = new DNode<T>(null, null, null);
        mHead.prev = mHead.next = mHead;
        mCount = 0;
    }


    /**
     * 返回节点数目
     *
     * @return
     */
    public int size() {
        return mCount;
    }

    /**
     * 返回链表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return mCount == 0;
    }

    /**
     * 获取第index位置节点
     *
     * @param index
     * @return
     */
    private DNode<T> getNode(int index) {
        //判断index是否越界
        if (index < 0 || index >= mCount) {
            throw new IndexOutOfBoundsException("越界啦");
        }

        //判断是正向查找，还是反向查找
        if (index <= mCount / 2) {
            //正向查找
            DNode<T> nNode = mHead.next;
            for (int i = 0; i < index; i++) {
                nNode = nNode.next;
            }
            return nNode;
        }

        //反向查找
        DNode<T> pNode = mHead.prev;
        int pIndex = mCount - index - 1;
        for (int j = 0; j < pIndex; j++) {
            pNode = pNode.prev;
        }
        return pNode;
    }

    /**
     * 获取第index位置节点值
     *
     * @param index
     * @return
     */
    public T get(int index) {
        return this.getNode(index).value;
    }

    /**
     * 获取第1个位置的节点值
     *
     * @return
     */
    public T getFirst() {
        return this.get(0);
    }

    /**
     * 获取最后一个位置的节点值
     *
     * @return
     */
    public T getLast() {
        return this.get(mCount - 1);
    }

    /**
     * 插入数据到index位置
     *
     * @param index
     * @param t
     */
    public void insert(int index, T t) {
        if (mCount == 0) {
            DNode<T> node = new DNode<>(mHead.prev, mHead, t);
            //***这两步也不能弄反
            mHead.next.prev = node;
            mHead.next = node;
            mCount++;
            return;
        }
        // mh     a(0) b(1) c(2) d(3)
        DNode<T> inode = getNode(index);
        DNode<T> cNode = new DNode<>(inode.prev, inode, t);
        inode.prev.next = cNode;
        //这一步可以不需要？？？
        //inode.next = cNode;
        mCount++;
        return;
    }

    /**
     * 插入到表头
     *
     * @param t
     */
    public void insertFirst(T t) {
        insert(0,t);
    }

    /**
     * 插入到表尾
     *
     * @param t
     */
    public void appendLast(T t) {
        DNode<T> node = new DNode<>(mHead.prev, mHead, t);
        //***这两步顺序不能弄错，不然整个链表就会错乱
        //末尾节点的下一个节点指向新增
        mHead.prev.next = node;
        //头节点的上一个节点指向新增节点；
        mHead.prev = node;
        mCount++;
        return;
    }

    /**
     * 删除到某个位置
     *
     * @param index
     */
    public void del(int index) {
        DNode<T> node = getNode(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        mCount--;
    }

    /**
     * 删除表头
     */
    public void deleteFirst() {
        del(0);
    }

    /**
     * 删除表尾
     */
    public void deleteLast() {
        del(mCount - 1);
    }

    private class DNode<T> {

        private DNode prev;

        private DNode next;

        private T value;

        public DNode(DNode prev, DNode next, T value) {
            this.prev = prev;
            this.next = next;
            this.value = value;
        }
    }
}
